Optimisation quadratique

Optimisation quadratique dans un espace à deux dimensions (x1, x2) contraint dans un polygone convexe. Gauche : l'ensemble admissible E contient le minimum absolu. Droite : l'ensemble admissible E ne contient pas le minimum absolu. Haut : vue en perspective. Bas : vue plane, la valeur de y étant représentée par des courbes de niveau.

En optimisation mathématique, un problème d'optimisation quadratique est un problème d'optimisation dans lequel on minimise (ou maximise) une fonction quadratique sur un polyèdre convexe. Les contraintes peuvent donc être décrites par des fonctions linéaires (on devrait dire affines). L'optimisation quadratique est la discipline qui étudie ces problèmes. L'optimisation linéaire peut être vue comme un cas particulier de l'optimisation quadratique.

Ce problème est NP-difficile dans le cas général. Dans le cas particulier de la minimisation d'une fonction objectif convexe, le problème est polynomial et on parle d'optimisation quadratique convexe ; une discipline déjà très riche aux propriétés mieux connues.

Lorsque le critère et les contraintes du problème d'optimisation sont quadratiques, on parle d'optimisation tout quadratique (en). Cette classe de problèmes contient toute l'optimisation polynomiale et est donc beaucoup plus générale que l'optimisation quadratique.